/*
 * @Author: szx
 * @Date: 2022-04-21 13:14:11
 * @LastEditTime: 2022-04-21 13:24:49
 * @Description:
 * @FilePath: \leetcode\剑指offerII\076\076.js
 */
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function (nums, k) {
    nums.sort((a, b) => b - a);
    return nums[k - 1];
};

// 堆排序？
var findKthLargest = function (nums, k) {
    // 先初始化，建立大顶堆
    let len = nums.length;
    for (let i = Math.floor(len / 2); i >= 0; i--) {
        heapify(nums, i, len);
    }
    const n = nums.length;
    for (let i = n - 1; i >= n - k; i--) {
        // 交换根节点和末尾节点
        swap(nums, 0, i);
        len--;
        heapify(nums, 0, len);
    }
    return nums[n - k];
};

function heapify(arr, i, len) {
    // 堆调整
    // 2i+1是左节点，2i+2是右节点，最大值的下标为当前节点
    const left = 2 * i + 1,
        right = 2 * i + 2;
    let largest = i;

    // 判断子节点是否存在，并找出最大的那个
    if (left < len && arr[left] > arr[largest]) largest = left;
    if (right < len && arr[right] > arr[largest]) largest = right;

    // 如果最大值不等于父节点（就是子节点比父节点大），那么就进行交换，并进行
    if (largest != i) {
        swap(arr, i, largest);
        heapify(arr, largest, len);
    }
}

function swap(arr, i, j) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
